package day03

import "sort"

// day03
//
// #### 860. 柠檬水找零
//
// https://leetcode.cn/problems/lemonade-change/
//
// ```go
func lemonadeChange(bills []int) bool {
	five, ten := 0, 0
	for i := 0; i < len(bills); i++ {
		if bills[i] == 5 {
			five++
		} else if bills[i] == 10 {
			five--
			ten++
		} else {
			if ten > 0 {
				ten--
				five--
			} else {
				five -= 3
			}
		}
		if five < 0 {
			return false
		}
	}
	return true
}

// ```
//
// 406. 根据身高重建队列
//
// https://leetcode.cn/problems/queue-reconstruction-by-height/
//
// ```go
func reconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(i, j int) bool {
		return people[i][0] > people[j][0] || people[i][0] == people[j][0] && people[i][1] < people[j][1]
	})
	ans := make([][]int, len(people))
	for _, v := range people {
		k := v[1]
		copy(ans[k+1:], ans[k:])
		ans[k] = v
	}
	return ans
}

// ```
//
// 452. 用最少数量的箭引爆气球
//
// https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
//
// ```go
func findMinArrowShots(points [][]int) int {
	sort.Slice(points, func(i, j int) bool {
		return points[i][0] < points[j][0]
	})
	ans := 1
	for i := 1; i < len(points); i++ {
		// r : 前一个气球的右边界
		// l : 后一个气球的左边界
		r := points[i-1][1]
		l := points[i][0]
		// 判断是否重合
		if l <= r {
			points[i][1] = min(points[i-1][1], points[i][1])
		} else {
			ans++
		}
	}
	return ans
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

//```
